package subject.dp;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class wordBreak {

    public boolean wordBreak1(String s, List<String> wordDict) {
        // 1. 将单词列表转为哈希集合（提高查询效率）
        Set<String> wordDictSet = new HashSet<>(wordDict);

        // 2. 创建DP数组（长度=字符串长度+1）
        boolean[] dp = new boolean[s.length() + 1];

        // 3. 初始化：空字符串可拆分
        dp[0] = true;

        // 4. 遍历所有子串结束位置（从1到字符串长度）
        for (int i = 1; i <= s.length(); i++) {
            // 5. 检查所有可能的拆分点j
            for (int j = 0; j < i; j++) {
                // 6. 关键判断：
                //    - 前j个字符可拆分（dp[j]==true）
                //    - 且子串s[j..i-1]在单词列表中
                if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                    dp[i] = true; // 标记可拆分
                    break; // 找到一种拆分即可跳出内层循环
                }
            }
        }
        // 7. 返回整个字符串是否可拆分
        return dp[s.length()];
    }
}
